A packet relay device includes a plurality of communication ports therein. A packet is received via one of the plurality of communication ports, and stored in a queue. The stored packet is read from the queue in a first-in first-out manner. One or more communication ports via which the packet is to be transmitted are determined and the packet is transferred to the determined output ports. When the packet relay device includes a plurality of queues, a queue scheduling for handling these plurality of queues becomes a problem. The deficit round robin (DRR) scheme has been proposed as a queue scheduling method which allows a plurality of queues to be fairly handled, and this DRR scheme is also employed in packet relay devices (for example, see Japanese Laid-open Patent Publication No. 11-252097).
In the DRR scheme, a quantum value, which is a quota of an amount of data read from each queue in one read process, is determined in advance. That is, data of an amount of the quantum value has been read from one queue, the read process on the queue terminates to shift to the read process on another queue. When an amount of data stored in a queue is less than the quantum value, the read process on the queue terminates upon completion of reading entire data stored in the queue. A read process on each queue is performed on a packet-by-packet basis, and thus, practically, the read process may not terminate upon completion of reading an amount of data exactly corresponding to the quantum value. Instead, the read process on the queue may be prolonged until completion of reading a packet which has being read at a time when the amount of data corresponding to the quantum value has been read. An amount of data read beyond the quantum value is referred to as a deficit value. A quota of an amount of data for the next read process on the queue is calculated by subtracting the deficit value from the quantum value. By repeating this operation, an average amount of data obtained by one read process on each queue becomes close to the quantum value. Thus, the DRR scheme is considered as a fair queue scheduling method.